﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main()
        {
            Test();
        }
        static void Test()
        {
            int tickCount = Environment.TickCount;
            double[] resultData = GetTop10000();
            Console.WriteLine("运算耗时：{0}", Environment.TickCount - tickCount);

            for (int i = 0; i < resultData.Length; i += resultData.Length / 10)
            {
                Console.WriteLine("返回结果[{0}]={1}", i, resultData[i]);
            }
        }


        static double[] GetTop10000()
        {
            int count = 0;
            const int resultCount = 10000;
            const int numberCount = 1000000000;
            bool IsDescending= true;
            IComparer<double> cmp1; //regual 
            IComparer<double> cmp2;
            Random r = new Random(1000); // 随机数种子固定，这样保证大家测试的数据一致

            double[] maxAfterMerge = new double[resultCount];//合并后的最大
            double[] maxBeforeMerge = new double[resultCount];//合并前的最大
            double[] current = new double[resultCount];//当前
            double[] temp;//交换数组用的
            int lastArrayCount = 0;//最后零头数组的长度

            //前10000个没什么好商量的，直接拿出来排序
            for (int i = 0; i < resultCount; i++)
            {
                maxBeforeMerge[i] = r.NextDouble();
            }
            count += resultCount;

            Array.Sort(maxBeforeMerge);//直接快排，省力

            while (true)
            {
                double currentMin = maxBeforeMerge[0];//取出当前10000个值中最小的
                for (int i = 0; i < resultCount; i++)
                {
                    double d;
                    do
                    {
                        if (count++ == numberCount)
                        {
                            lastArrayCount = i;
                            goto label;//退出3层循环，太麻烦，直接goto，要代码漂亮的把while(true)部分拉出来做个方法，这里return
                        }
                        d = r.NextDouble();
                    } while (d <= currentMin);//比有效数据最小的还小的值，直接跳过
                    current[i] = d;

                }

                if (IsDescending)
                    Array.Sort(current, cmp1);//直接快排，省力
                else
                    Array.Sort(current, cmp2);//直接快排，省力

                Merge(maxAfterMerge, maxBeforeMerge, current);//合并两个排序数组
                temp = maxAfterMerge;//交换。。。
                maxAfterMerge = maxBeforeMerge;
                maxBeforeMerge = temp;

            }
        label:
            if (lastArrayCount == 0)//正好是整的
            {
                Array.Reverse(maxBeforeMerge);
                return maxBeforeMerge;
            }

            Array.Sort(current, 0, lastArrayCount);//排序零头，直接快排，省力

            Merge(maxAfterMerge, maxBeforeMerge, current, lastArrayCount);//合并两个排序数组，其中一个是零头
            Array.Reverse(maxAfterMerge);
            return maxAfterMerge;
        }

        static void Merge(double[] max, double[] x, double[] y)
        {
            int xIndex = x.Length - 1;
            int yIndex = y.Length - 1;
            for (int i = max.Length - 1; i >= 0; i--)
            {
                if (x[xIndex] > y[yIndex])
                {
                    max[i] = x[xIndex--];
                }
                else
                {
                    max[i] = y[yIndex--];
                }
            }
        }

        static void Merge(double[] max, double[] x, double[] y, int yCount)
        {
            int xIndex = x.Length - 1;
            int yIndex = yCount - 1;
            for (int i = max.Length - 1; i >= 0; i--)
            {
                if (x[xIndex] > y[yIndex])
                {
                    max[i] = x[xIndex--];
                }
                else
                {
                    max[i] = y[yIndex--];
                    if (yIndex == -1)
                    {
                        Buffer.BlockCopy(x, xIndex - max.Length + i, max, 0, max.Length - i);
                        return;
                    }
                }
            }
        }

    }
}
